#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

typedef int ElemType;
typedef struct {
    ElemType lenth;
    ElemType *str;
} SqList;

void InitSqList(SqList &T, ElemType lenth) {
    T.lenth = lenth;
    T.str = (ElemType *) malloc(sizeof(ElemType) * T.lenth);
    /**随机数必备过程*/
//    time(NULL);
//    for (int i = 0; i < T.lenth; i++) {
//        T.str[i] = rand() % 100;
//    }
//    ElemType a[10] = {10, 67, 34, 19, 23, 24, 78, 5, 62, 2};
    ElemType *a = new ElemType[T.lenth]{10, 67, 34, 19, 23, 24, 78, 5, 62, 2};
    for (int i = 0; i < 10; i++) {
        T.str[i] = a[i];
    }
}

void array_print(SqList T) {
    for (int i = 0; i < T.lenth; i++) {
        printf("%2d ", T.str[i]);
    }
    printf("\n");
}

int compare(const void *left, const void *right) {
    return *(int *) left - *(int *) right;
}

//1.从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删元素的值。
//空出的位置由最后一个元素填补，若顺序表为空，则显示出错误信息并退出运行。
bool DeleteSqList(SqList &T, int &x) {
    if (T.str == NULL || T.lenth == 0) {
        return false;
    }
    int pos = 0;
    x = T.str[pos];
    for (int i = 1; i < T.lenth; i++) {
        if (x > T.str[i]) {
            pos = i;
            x = T.str[pos];
        }
    }

    T.str[pos] = T.str[T.lenth - 1];
    T.lenth--;
    return true;
}

//2.设计一个高效算法，将顺序表L的元素逆置，要求算法的空间复杂度为O(1).
void ReverseList(SqList &T) {
    for (int i = 0, j = T.lenth - 1; i <= j; i++, j--) {
        T.str[i] ^= T.str[j];
        T.str[j] ^= T.str[i];
        T.str[i] ^= T.str[j];
    }
    array_print(T);
}

//3.对长度为n的顺序表L，编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，
// 该算法删除线性表中所有值为x的数据元素。
void DeleteSpecifiedValue(SqList &T, ElemType x) {
//2, 67, 34, 1, 2, 24, 78, 5, 62, 2
//67, 34, 1, 2, 24, 78, 5, 62, 2
/**解法一*/
/*    for (int i = 0; i < T.lenth; i++) {
        if (T.str[i] == x) {
            for (int j = i; j < T.lenth - 1; j++) {
                T.str[j] = T.str[j + 1];
            }
            T.lenth--;
        }
    }*/
/**解法二*/
/*    int i = 0, k = 0;//k记录x元素的个数
    while (i < T.lenth) {
        if (T.str[i] == x) {
            k++;
        } else {
            T.str[i - k] = T.str[i];//当前元素前移k个位置
        }
        i++;
    }
    T.lenth -= k;//顺序表的长度递减*/

/**解法三*/
    int k = 0, i;
    for (i = 0; i < T.lenth; i++) {
        if (T.str[i] != x) {
            T.str[k] = T.str[i];
            k++;//不等于x的元素增一
        }
    }
    T.lenth = k;//顺序表的长度就等于k
    array_print(T);
}

//4.从有序顺序表中删除其值在给定值s与t之间(要求s<t)的所有元素，
// 若s或t不合理或顺序表为空，则显示出错信息并退出运行。

bool DeleteSpecifiedValueSection(SqList &T, ElemType s, ElemType t) {
    if (s >= t || T.lenth == 0) {
        return false;
    }
    qsort(T.str, T.lenth, sizeof(ElemType), compare);
    /**个人解法一*/
/*    int k = 0;
    for (int i = 0; i < T.lenth; i++) {
        if (T.str[i] < s || T.str[i] > t) {
            T.str[k++] = T.str[i];
        }
    }
    T.lenth = k;*/
    /**解法二
     * 思想：因为是有序表，所以删除的元素必定是相连的整体。
     * 先寻找值大于或等于s的第一个元素（第一个删除的元素），
     * 然后寻找值大于t的第一个元素（最后删除的元素的下一个元素）
     * 要将这段元素删除，只需直接将后面的元素前移即
     * */
    int i, j;
    for (i = 0; i < T.lenth && T.str[i] < s; i++);//寻找值大于或等于s的第一个元素
    if (i >= T.lenth) {
        return false;//若所有制均小于s值则返回false
    }
    for (j = i; j < T.lenth && T.str[j] <= t; j++);//寻找值大于t的第一个元素
    for (; j < T.lenth; i++, j++) {
        T.str[i] = T.str[j];
    }
    T.lenth = i;
    return true;

}

//5.从顺序表中删除其值在给定值s与t之间（包含s和t，要求s<t）的所有元素，若s或t不合理或顺序表为空，则显示出错信息并退出运行。
bool Del_s_t(SqList &T, ElemType s, ElemType t) {
    qsort(T.str, T.lenth, sizeof(ElemType), compare);
    array_print(T);
    int i, k = 0;
    if (T.lenth == 0 || s >= t) {
        return false;
    }
    for (i = 0; i < T.lenth; i++) {
        if (T.str[i] >= s && T.str[i] <= t) {
            k++;
        } else {
            T.str[i - k] = T.str[i];//当前元素前移k个位置
        }
    }
    T.lenth -= k;
    return true;
}

//6.从有序顺序表中删除所有其值重复的元素，使表中所有元素的值不同。
void Delete_Same(SqList &T) {

    if (T.lenth == 0) {
        return;
    }
    qsort(T.str, T.lenth, sizeof(ElemType), compare);
    int i, j;
    for (i = 0, j = 1; j < T.lenth; j++) {
        if (T.str[i] != T.str[j]) {
            T.str[++i] = T.str[j];
        }
    }
    T.lenth = i + 1;
}

//9.线性表（a1,a2,a3,...,an）中的元素递增有序且按顺序存储于计算机内。
// 要求设计一个算法，完成用最少时间在表中查找数值为x的元素，
//二分查找+插入
int swap(int &a, int &b) {
    a ^= b;
    b ^= a;
    a ^= b;
}

void Delete_List(SqList &T, int data) {
    qsort(T.str, T.lenth, sizeof(ElemType), compare);
    array_print(T);
    int mid, high, low;
    low = 0, high = T.lenth - 1;
    bool flag = false;
    while (low <= high) {
        mid = (low + high) / 2;
        if (T.str[mid] > data) {
            high = mid - 1;
        } else if (T.str[mid] < data) {
            low = mid + 1;
        } else {
            //若最后一个元素与data相等，则不存在与后继元素交换的可能
            if (T.str[mid] == data && mid != T.lenth - 1) {
                swap(T.str[mid], T.str[mid + 1]);
                flag = true;
                break;
            } else {
                return;
            }
        }
    }
    // 若找到，则将其与后继元素位置相交换，若找不到，则将其插入表中并使表中元素仍递增有序。
    if (!flag) {
        int i;
        for (i = T.lenth - 1; T.str[i] > data; i--) T.str[i + 1] = T.str[i];
        T.str[i + 1] = data;
        T.lenth++;
    }
}

int main() {
    /**第一题*/
    /*SqList T;
    InitSqList(T, 10);
    array_print(T);
    int data = NULL;
    DeleteSqList(T, data);
    if (data != NULL) {
        printf("data=%d\n", data);
    } else {
        printf("Delete failed\n");
    }
    array_print(T);*/

    /**第二题*/
/*    SqList T;
    InitSqList(T, 10);
    array_print(T);
    ReverseList(T);*/
    /**第三题*/
/*    SqList T;
    InitSqList(T, 10);
    array_print(T);
    DeleteSpecifiedValue(T, 2);*/
    /**第四题*/
/*    SqList T;
    InitSqList(T, 10);
    array_print(T);
    bool flag=DeleteSpecifiedValueSection(T, 5, 75);
    if(flag){
        printf("Delete Successfully\n");
        array_print(T);
    }else{
        printf("Delete failed\n");
    }*/

    /**第五题*/
/*    SqList T;
    InitSqList(T,10);
    Del_s_t(T,1,9);
    array_print(T);*/

    /**第六题*/
/*    SqList T;
    InitSqList(T, 10);
    array_print(T);
    Delete_Same(T);
    array_print(T);*/

    /**第九题*/
    SqList T;
    InitSqList(T, 10);
    array_print(T);
    Delete_List(T, 65);
    array_print(T);
    return 0;
}
